package com.liyafeng.algorithm.sword2offer;

/**
 * Created by liyafeng on 2018/2/26.
 */

public class N41_TwoNumbersWithSum {

    /**
     * 给定一个递增数组，找出和为S的两个数字，如果有多个答案，则输出任意一个
     * ================思路================
     * 首先最简单的方法是依次遍历数组，然后S减去这个元素，再在剩下的元素中查找这个数
     * 查找我们可以用二分法查找，这样时间复杂度是O(nlogn)
     * 第二个思路就是将元素放入hashmap，查找用hashmap，这个时间复杂度是O(n)
     * 但是这种需要额外的空间，n
     * 第三种思路就是从数组中找规律，从递增中找规律，一个head指针，一个tail指针
     * 求和，大于15，那么我们肯定要减小一个元素，只能将tail前移一位，这个时候如果和
     * 小于15，那么只能将head后移来增加和的大小。
     *
     * =================考点=================
     * 考察找规律，知道一个递增数组中两个元素和的变化规律是怎样的
     *
     * ===========拓展==================
     * 求一个递增序列中和为s的所有连续序列。
     * 这个还是一个small指针指向第一个元素，big指向第二个，和小了就后移big，大了就后移small
     * @param args
     */
    public static void main(String[] args) {

    }
}
